{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/keys-and-rooms\n",
    "\n",
    "\n",
    "Runtime: 16 ms, faster than 71.79% of C++ online submissions for Keys and Rooms.\n",
    "Memory Usage: 11.5 MB, less than 12.18% of C++ online submissions for Keys and Rooms.\n",
    "\n",
    "\n",
    "```cpp\n",
    "#include <vector>\n",
    "#include <algorithm>\n",
    "#include <set>\n",
    "#include <iostream>\n",
    "#include <unordered_map>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "class Solution\n",
    "{\n",
    "public:\n",
    "    bool canVisitAllRooms(vector<vector<int>> &rooms)\n",
    "    {\n",
    "        //6:30\n",
    "        int allRooms = rooms.size();\n",
    "        set<int> keySet;\n",
    "        set<int> tempKeys{0};\n",
    "        while (tempKeys.size())\n",
    "        {\n",
    "            auto key = tempKeys.begin();\n",
    "            set<int> moreKeys = convertToSet(rooms[*key]);\n",
    "            keySet.insert(*key);\n",
    "            tempKeys.erase(key);\n",
    "            updateSet(tempKeys, moreKeys, keySet);\n",
    "        }\n",
    "        if (keySet.size() == allRooms)\n",
    "        {\n",
    "            return true;\n",
    "        }\n",
    "        else\n",
    "        {\n",
    "            return false;\n",
    "        }\n",
    "        //7:04\n",
    "    }\n",
    "    set<int> convertToSet(vector<int> v)\n",
    "    {\n",
    "        set<int> s;\n",
    "\n",
    "        for (int x : v)\n",
    "        {\n",
    "            s.insert(x);\n",
    "        }\n",
    "\n",
    "        return s;\n",
    "    }\n",
    "    void updateSet(set<int> &tempKeys, set<int> &moreKeys, set<int> &keySet)\n",
    "    {\n",
    "        for (auto key : moreKeys)\n",
    "        {\n",
    "            if (keySet.find(key) == keySet.end())\n",
    "            {\n",
    "                tempKeys.insert(key);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}